/*
 * Copyright 2012 The Netty Project
 *
 * The Netty Project licenses this file to you under the Apache License,
 * version 2.0 (the "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at:
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations
 * under the License.
 */

package io.netty.buffer;

/**
 * 这个类的对象就是用来包装8KB内存的
 * @param <T>
 */
final class PoolSubpage<T> implements PoolSubpageMetric {
    /**
     * 该8KB内存是从哪个PoolChunk中分配的
     */
    final PoolChunk<T> chunk;
    /**
     * 分配的这块8KB内存在Chunk二叉树数组中的下标索引
     */
    private final int memoryMapIdx;
    /**
     * 这个PoolSubpage包装的8KB内存在Chunk中的内存偏移量的大小
     */
    private final int runOffset;
    /**
     * 这个PoolSubpage的大小，也就是8KB
     */
    private final int pageSize;
    /**
     * 一个PoolSubpage是8KB，最多可以分配成512个16B，所以数组容量最大为512
     * 而一个long类型有64位，8个long就有512位，所以用容量为8的long数组就可以有512个索引，也就可以表示PoolSubpage数组中哪个位置使用了，哪个位置没有使用，用0和1来区分。这个就是位图
     */
    private final long[] bitmap;
    /**
     * 前驱节点指针
     */
    PoolSubpage<T> prev;
    /**
     *下一个节点的指针
     */
    PoolSubpage<T> next;
    /**
     * true表示当前subpage是存活状态
     * false表示当前subpage是释放状态（Subpage内部管理的内存都是释放了）
     */
    boolean doNotDestroy;
    /**
     * 当前PoolSubpage管理的规格大小
     */
    int elemSize;
    /**
     * 不变的：当前subpage最多可给业务多少小块内存
     */
    private int maxNumElems;
    /**
     * bitmap多少个元素能够满足使用
     */
    private int bitmapLength;
    /**
     * 初始值是0，申请内存时，会使用这个字段，表示下一个可用的下个位图下标值
     * 当某个ByteBuf占用的内存还给当前subpage时，这个内存占用的bit的索引值会设置给这个字段，下次再申请直接就使用nextAvail就可以了
     */
    private int nextAvail;
    /**
     * 会变的：当前subpage最多可给业务多少小块内存
     */
    private int numAvail;


    /** Special constructor that creates a linked list head */
    PoolSubpage(int pageSize) {
        chunk = null;
        memoryMapIdx = -1;
        runOffset = -1;
        elemSize = -1;
        this.pageSize = pageSize;
        bitmap = null;
    }

    /**
     *
     * @param head Arena范围内的pools符合当前规格的head节点
     * @param chunk PoolChunk对象
     * @param memoryMapIdx 当前subpage占用的叶子节点的id号
     * @param runOffset 计算出当前叶子节点的管理的内存在整个内存的偏移位置
     * @param pageSize page大小默认是8192
     * @param elemSize 规格化后的内存大小
     */
    PoolSubpage(PoolSubpage<T> head, PoolChunk<T> chunk, int memoryMapIdx, int runOffset, int pageSize, int elemSize) {
        this.chunk = chunk;
        this.memoryMapIdx = memoryMapIdx;
        this.runOffset = runOffset;
        this.pageSize = pageSize;
        // pageSize/16/64
        // pageSize/16 是因为tiny最小规格是16字节，以最小规格划分的话需要多少个bit才能展示出这个内存使用情况
        // 除以64是因为long是8字节，1字节是8位
        // 最终长度就是8
        bitmap = new long[pageSize >>> 10];
        init(head, elemSize);
    }

    void init(PoolSubpage<T> head, int elemSize) {
        doNotDestroy = true;
        this.elemSize = elemSize;
        if (elemSize != 0) {
            // 计算出subpage按照elemSize划分一共可以划分多少小块
            maxNumElems = numAvail = pageSize / elemSize;
            nextAvail = 0;
            // maxNumElems/64，计算出当前maxNumElems需要long数组的多少
            // 当elemSize等于32字节时，计算出来bitmapLength位4
            bitmapLength = maxNumElems >>> 6;
            // 如果计算出来的有余数就把bitmapLength++
            if ((maxNumElems & 63) != 0) {
                bitmapLength ++;
            }
            // 根据长度初始化bitmap
            for (int i = 0; i < bitmapLength; i ++) {
                bitmap[i] = 0;
            }
        }
        // 头插法head
        addToPool(head);
    }

    /**
     * Returns the bitmap index of the subpage allocation.
     */
    long allocate() {
        if (elemSize == 0) {
            return toHandle(0);
        }
        /*
         * 条件1成立：说明当前Subpage管理的一页内存全都划分完了
         * 条件2成立：虽然Subpage管理的一页内存还有剩余部分但是当前subpage是释放状态所以不能分配
         */
        if (numAvail == 0 || !doNotDestroy) {
            return -1;
        }
        // 从bitmap中查找一个可用的bit的索引值
        final int bitmapIdx = getNextAvail();
        // 设置bitmap中的bit的值
        int q = bitmapIdx >>> 6;
        int r = bitmapIdx & 63;
        assert (bitmap[q] >>> r & 1) == 0;
        bitmap[q] |= 1L << r;
        // 当前subpage没有可给业务分配的小块内存了则从数组中移除，减少numAvail是因为要更新当前subpage最多可给业务多少小块内存数量更新
        if (-- numAvail == 0) {
            removeFromPool();
        }
        // long类型：高32位是subpage内存的bit索引值，低32位为当前subpage占用chunk叶子节点的id值
        return toHandle(bitmapIdx);
    }

    /**
     * @return {@code true} if this subpage is in use.
     *         {@code false} if this subpage is not used by its chunk and thus it's OK to be released.
     */
    boolean free(PoolSubpage<T> head, int bitmapIdx) {
        if (elemSize == 0) {
            return true;
        }
        // 对应的bitmap的位置设置为0
        int q = bitmapIdx >>> 6;
        int r = bitmapIdx & 63;
        assert (bitmap[q] >>> r & 1) != 0;
        bitmap[q] ^= 1L << r;
        // 更新nextAvail
        setNextAvail(bitmapIdx);
        // 如果numAvail自增之前等于0，那么说明这个Subpage被从PoolSubpage数组中移除了，现在释放就有了把他添加回PoolSubpage数组中
        if (numAvail ++ == 0) {
            addToPool(head);
            return true;
        }
        // 条件成立：这个Subpage还有没有被释放的部分
        if (numAvail != maxNumElems) {
            // 返回true
            return true;
        } else { // 这个Subpage完全释放了没有任何线程用了
            if (prev == next) {
                // 如果池中只剩下该Subpage，则不要删除
                return true;
            }
            // 如果子页面池中还有其他子页面，则从子页面池中删除该子页面
            doNotDestroy = false;
            // 从PoolSubpage数组中移除这个Subpage
            removeFromPool();
            // 返回false
            return false;
        }
    }

    private void addToPool(PoolSubpage<T> head) {
        assert prev == null && next == null;
        prev = head;
        next = head.next;
        next.prev = this;
        head.next = this;
    }

    private void removeFromPool() {
        assert prev != null && next != null;
        prev.next = next;
        next.prev = prev;
        next = null;
        prev = null;
    }

    private void setNextAvail(int bitmapIdx) {
        nextAvail = bitmapIdx;
    }

    private int getNextAvail() {
        int nextAvail = this.nextAvail;
        if (nextAvail >= 0) {
            this.nextAvail = -1;
            return nextAvail;
        }
        return findNextAvail();
    }

    private int findNextAvail() {
        final long[] bitmap = this.bitmap;
        final int bitmapLength = this.bitmapLength;
        for (int i = 0; i < bitmapLength; i ++) {
            long bits = bitmap[i];
            if (~bits != 0) {
                return findNextAvail0(i, bits);
            }
        }
        return -1;
    }

    private int findNextAvail0(int i, long bits) {
        final int maxNumElems = this.maxNumElems;
        final int baseVal = i << 6;

        for (int j = 0; j < 64; j ++) {
            if ((bits & 1) == 0) {
                int val = baseVal | j;
                if (val < maxNumElems) {
                    return val;
                } else {
                    break;
                }
            }
            bits >>>= 1;
        }
        return -1;
    }

    private long toHandle(int bitmapIdx) {
        return 0x4000000000000000L | (long) bitmapIdx << 32 | memoryMapIdx;
    }

    @Override
    public String toString() {
        final boolean doNotDestroy;
        final int maxNumElems;
        final int numAvail;
        final int elemSize;
        if (chunk == null) {
            // This is the head so there is no need to synchronize at all as these never change.
            doNotDestroy = true;
            maxNumElems = 0;
            numAvail = 0;
            elemSize = -1;
        } else {
            synchronized (chunk.arena) {
                if (!this.doNotDestroy) {
                    doNotDestroy = false;
                    // Not used for creating the String.
                    maxNumElems = numAvail = elemSize = -1;
                } else {
                    doNotDestroy = true;
                    maxNumElems = this.maxNumElems;
                    numAvail = this.numAvail;
                    elemSize = this.elemSize;
                }
            }
        }

        if (!doNotDestroy) {
            return "(" + memoryMapIdx + ": not in use)";
        }

        return "(" + memoryMapIdx + ": " + (maxNumElems - numAvail) + '/' + maxNumElems +
                ", offset: " + runOffset + ", length: " + pageSize + ", elemSize: " + elemSize + ')';
    }

    @Override
    public int maxNumElements() {
        if (chunk == null) {
            // It's the head.
            return 0;
        }

        synchronized (chunk.arena) {
            return maxNumElems;
        }
    }

    @Override
    public int numAvailable() {
        if (chunk == null) {
            // It's the head.
            return 0;
        }

        synchronized (chunk.arena) {
            return numAvail;
        }
    }

    @Override
    public int elementSize() {
        if (chunk == null) {
            // It's the head.
            return -1;
        }

        synchronized (chunk.arena) {
            return elemSize;
        }
    }

    @Override
    public int pageSize() {
        return pageSize;
    }

    void destroy() {
        if (chunk != null) {
            chunk.destroy();
        }
    }
}
